package ali;

/**
 *
 * @author wxh
 */
public class Solution_8 {

	// 解法一：贪心算法
	public int maxSubArray(int[] nums) {
		int result = nums[0];
		int sum = 0;
		for (int num : nums) {
			if (sum > 0) {
				//sum > 0，说明前面有加总的值，直接把当前值加到sum
				sum = sum + num;
			} else {
				//sum <= 0，sum + num就没有意义了，因为如果sum=-1，而num=1，相加为0，反而变小了，如果num为负数，那就更小了，所以直接把当前值赋给sum即可
				sum = num;
			}
			//比较 sum 和 result的大小，将最大值置为result。这是为了避免因为num为负数，导致sum = sum + num后， sum变小
			result = sum > result ? sum : result;
		}
		return result;
	}

	public static void main(String[] args) {
		Solution_8 solution_8 = new Solution_8();
		System.out.println(solution_8.maxSubArray(new int[] {1, 2, 3, -2, -1, -3}));
	}

}